#include <bits/stdc++.h>
using namespace std;
int getMaxValue_solution(const int* values,int rows,int cols)
{
    if(values == nullptr||rows<=0||cols<=0)
        return 0;
    int** maxValues = new int*[rows];
    for(int i=0;i<rows;++i)
        maxValues[i] = new int[cols];
    for(int i = 0;i<rows;i++)
    {
        for(int j = 0;j<cols;j++)
        {
            int left = 0,up = 0;
            if(i>0)
                up = maxValues[i-1][j];
            if(j>0)
                left = maxValues[i][j-1];
            maxValues[i][j] = max(left,up)+values[i*cols+j];
        }
    }
    int maxValue = maxValues[rows-1][cols-1];
    for(int i=0;i<rows;i++)
    {
        for(int j=0;j<cols;j++)
            cout<<maxValues[i][j]<<" ";
        cout<<"\n";
    }
    for(int i = 0;i<rows;i++)
        delete[] maxValues[i];
    delete [] maxValues;
    return maxValue;
}
int max_value(vector<int>&a,int col,int row){
    if(row<=0||col<=0)
        return 0;
    vector<int>max_value_list(row*col,0) ;
    int i,j;
    for(i=0;i<col;i++)
    {

        for(j=0;j<row;j++)
        {
            int left = 0,right = 0;
            if(i>0)
                left = max_value_list[(i-1)*col+j];
            if(j>0)
                right = max_value_list[i*col+j-1];
            max_value_list[i*col+j] = max(left,right)+a[i*col+j];
        }
    }
    return max_value_list[(i-1)*col+j-1];
}
int show(vector<int>&a,int col,int row)
{
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++)
        {
            cout<<a[i*row+j]<<" ";
        }
        cout<<"\n";
    }
}
int main() {
    vector<int> a={1,10,3,8,12,2,9,6,5,7,4,11,3,7,16,5};
    int m=4,n=4;
    int* data = new int[16]{1,10,3,8,12,2,9,6,5,7,4,11,3,7,16,5};
//    cout<<getMaxValue_solution(data,m,n)<<"\n";
    cout<<max_value(a,m,n);
}